20220406-TIL

오늘 알고리즘 문제는 파일을 합치는 데에 필요한 최소 비용을 구해야 하는 문제였다.

• 파일 합치기 문제는 ‘특정 구간의 파일 합치기’ 를 부분 문제로 두는 식으로 풀었다.
• 처음에는 합치는 비용만 최소화하면 되는 줄 알고 우선순위 큐로 풀어보려 했었다..
  ('동적 계획법 문제가 맞나?' 싶었는데 인접한 파일들을 하나씩 합쳐야 하는 문제였음;)
• ‘i ~ j번 파일 합치기’ 문제를 중간 점 k를 기준으로 나눠서 푸는 식으로도 접근했다.
  (재귀 함수 틀은 괜찮았는데 세부 사항을 제대로 구현 못함.. -> 결국엔 검색해서 품;)
• 3중 반복문 풀이와 크누스 최적화 풀이는 내일 다시 살펴보기로 했다. (쉽지 않음;)